{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Rapidly-Exploring Random Tree (RRT) Planning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Notebook Setup\n",
    "The following cell will install Drake, checkout the underactuated repository, and set up the path (only if necessary).\n",
    "- On Google's Colaboratory, this **will take approximately two minutes** on the first time it runs (to provision the machine), but should only need to reinstall once every 12 hours.  Colab will ask you to \\\"Reset all runtimes\\\"; say no to save yourself the reinstall.\n",
    "- On Binder, the machines should already be provisioned by the time you can run this; it should return (almost) instantly.\n",
    "\n",
    "More details are available [here](http://underactuated.mit.edu/drake.html)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "try:\n",
    "    import pydrake\n",
    "    import underactuated\n",
    "except ImportError:\n",
    "    !curl -s https://raw.githubusercontent.com/RussTedrake/underactuated/master/scripts/setup/jupyter_setup.py > jupyter_setup.py\n",
    "    from jupyter_setup import setup_underactuated\n",
    "    setup_underactuated()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# python libraries\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Description\n",
    "In this problem set, you will write code for the Rapidly-Exploring Random Tree (RRT), which is an algorithm designed to efficiently search nonconvex, high-dimensional spaces by randomly building a space-filling tree. Building on this implementation you will also implement RRT*, a variant of RRT that converges towards an optimal solution.\n",
    "\n",
    "RRTs easily handle problems with obstacles and differential constraints (nonholonomic and kinodynamic) and can also be viewed as a method to generate open-loop trajectories for nonlinear systems with state constraints. RRTs have been widely used in autonomous robotic motion planning. We will use the RRT to find a path from a starting location `start` to a goal location `goal` while avoiding `obstacles` in the form of circles. We will search over the 2D domain bounded by `bounds`. Take a look at the instantiation of the problem below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "start = np.array([11, 0]) # Start location\n",
    "goal = np.array([6, 8]) # Goal location\n",
    "\n",
    "obstacles = [ # circles parametrized by [x, y, radius]\n",
    "        np.array([9, 6, 2]),\n",
    "        np.array([9, 8, 1]),\n",
    "        np.array([9, 10, 2]),\n",
    "        np.array([4, 5, 2]),\n",
    "        np.array([7, 5, 2]),\n",
    "        np.array([4, 10, 1])\n",
    "] \n",
    "\n",
    "bounds = np.array([-2, 15]) # Bounds in both x and y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_scene(obstacle_list, start, goal):\n",
    "    ax = plt.gca()\n",
    "    for o in obstacle_list:\n",
    "        circle = plt.Circle((o[0], o[1]), o[2], color='k')\n",
    "        ax.add_artist(circle)\n",
    "    plt.axis([bounds[0]-0.5, bounds[1]+0.5, bounds[0]-0.5, bounds[1]+0.5])\n",
    "    plt.plot(start[0], start[1], \"xr\", markersize=10)\n",
    "    plt.plot(goal[0], goal[1], \"xb\", markersize=10)\n",
    "    plt.legend(('start', 'goal'), loc='upper left')\n",
    "    plt.gca().set_aspect('equal')\n",
    "    \n",
    "plt.figure()\n",
    "plot_scene(obstacles, start, goal)\n",
    "plt.tight_layout()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rapidly-Exploring Random Tree (RRT) Planning\n",
    "\n",
    "The RRT is constructed incrementally from samples drawn randomly from the search space and is inherently biased to grow towards large unsearched areas of the problem. The algorithm grows a tree rooted in the starting configuration, in our case the `start` location, through drawing random samples from the bounded search space. \n",
    "\n",
    "Remember that a tree consists of nodes containing data, in our case the position `p`, and a pointer to the parent node.\n",
    "When a new node is sampled, it is connected to the nearest node in the tree. If the path connecting the nearest node to the sampled node does not violate constraints, the new node is added to the tree with the nearest node as the parent of the new node. In our setting, this means that if the path connecting the sampled node and the nearest node crosses an obstacle, the new node is discarded. The expansion of the tree continues until a connection to the `goal` has been found or a maximum number of iterations `max_iter` have been executed.\n",
    "\n",
    "In most implementations the length of the path connecting a randomly sampled node and the nearest node is limited. We refer to this maximum distance as `max_extend_length`. Intuitively, `max_extend_length` limits the growth rate of the tree. \n",
    "\n",
    "While one can sample uniformly over the search space, it is common to bias sampling towards more promising regions. \n",
    "In our implementation, we introduce a small probability `goal_sample_rate` of sampling the goal as a new node instead of generating a sample uniformly over the search space. The higher this probability, the more greedily the tree grows towards the goal.\n",
    "\n",
    "Your task is to complete the RRT implementation below to find a collision-free path connecting `start` and `goal` without colliding with circular `obstacles`. We provide implementations of many helper functions such as generating random nodes, checking paths between nodes for collisions, and more.\n",
    "\n",
    "**These are the main steps of the first part of the exercise:**\n",
    "1. Familiarize yourself with the RRT class. Go through the code and understand what each method does and what the members of the class contain.\n",
    "2. Fill out the `final_path` method.\n",
    "3. Complete the `plan` method by following the instructions inside the method.\n",
    "\n",
    "Note that you only have to change the code where indicated by `# modify here`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class RRT:\n",
    " \n",
    "    class Node:\n",
    "        def __init__(self, p):\n",
    "            self.p = np.array(p)\n",
    "            self.parent = None\n",
    "\n",
    "    def __init__(self, start, goal, obstacle_list, bounds, \n",
    "                 max_extend_length=3.0, path_resolution=0.5, \n",
    "                 goal_sample_rate=0.05, max_iter=100):\n",
    "        self.start = self.Node(start)\n",
    "        self.goal = self.Node(goal)\n",
    "        self.bounds = bounds\n",
    "        self.max_extend_length = max_extend_length\n",
    "        self.path_resolution = path_resolution\n",
    "        self.goal_sample_rate = goal_sample_rate\n",
    "        self.max_iter = max_iter\n",
    "        self.obstacle_list = obstacle_list\n",
    "        self.node_list = []\n",
    "\n",
    "    def plan(self):\n",
    "        \"\"\"Plans the path from start to goal while avoiding obstacles\"\"\"\n",
    "        self.node_list = [self.start]\n",
    "        for i in range(self.max_iter):\n",
    "            # modify here: \n",
    "            # 1) Create a random node (rnd_node) inside \n",
    "            # the bounded environment\n",
    "            # 2) Find nearest node (nearest_node)\n",
    "            # 3) Get new node (new_node) by connecting\n",
    "            # rnd_node and nearest_node. Hint: steer\n",
    "            # 4) If the path between new_node and the\n",
    "            # nearest node is not in collision, add it to the node_list\n",
    "    \n",
    "            # Don't need to modify beyond here\n",
    "            # If the new_node is very close to the goal, connect it\n",
    "            # directly to the goal and return the final path\n",
    "            if self.dist_to_goal(self.node_list[-1].p) <= self.max_extend_length:\n",
    "                final_node = self.steer(self.node_list[-1], self.goal, self.max_extend_length)\n",
    "                if not self.collision(final_node, self.node_list[-1], self.obstacle_list):\n",
    "                    return self.final_path(len(self.node_list) - 1)\n",
    "        return None  # cannot find path\n",
    "\n",
    "    def steer(self, from_node, to_node, max_extend_length=np.inf):\n",
    "        \"\"\"Connects from_node to a new_node in the direction of to_node\n",
    "        with maximum distance max_extend_length\n",
    "        \"\"\"\n",
    "        new_node = self.Node(to_node.p)\n",
    "        d = from_node.p - to_node.p\n",
    "        dist = np.linalg.norm(d)\n",
    "        if dist > max_extend_length:\n",
    "            # rescale the path to the maximum extend_length\n",
    "            new_node.p  = from_node.p - d / dist * max_extend_length\n",
    "        new_node.parent = from_node\n",
    "        return new_node\n",
    "\n",
    "    def dist_to_goal(self, p):\n",
    "        \"\"\"Distance from p to goal\"\"\"\n",
    "        return np.linalg.norm(p - self.goal.p)\n",
    "\n",
    "    def get_random_node(self):\n",
    "        \"\"\"Sample random node inside bounds or sample goal point\"\"\"\n",
    "        if np.random.rand() > self.goal_sample_rate:\n",
    "            # Sample random point inside boundaries\n",
    "            rnd = self.Node(np.random.rand(2)*(self.bounds[1]-self.bounds[0]) + self.bounds[0])\n",
    "        else:  \n",
    "            # Select goal point\n",
    "            rnd = self.Node(self.goal.p)\n",
    "        return rnd\n",
    "    \n",
    "    @staticmethod\n",
    "    def get_nearest_node(node_list, node):\n",
    "        \"\"\"Find the nearest node in node_list to node\"\"\"\n",
    "        dlist = [np.sum(np.square((node.p - n.p))) for n in node_list]\n",
    "        minind = dlist.index(min(dlist))\n",
    "        return node_list[minind]\n",
    "    \n",
    "    @staticmethod\n",
    "    def collision(node1, node2, obstacle_list):\n",
    "        \"\"\"Check whether the path connecting node1 and node2 \n",
    "        is in collision with anyting from the obstacle_list\n",
    "        \"\"\"\n",
    "        p1 = node2.p\n",
    "        p2 = node1.p \n",
    "        for o in obstacle_list:\n",
    "            center_circle = o[0:2]\n",
    "            radius = o[2]\n",
    "            d12 = p2 - p1 # the directional vector from p1 to p2\n",
    "            # defines the line v(t) := p1 + d12*t going through p1=v(0) and p2=v(1)\n",
    "            d1c = center_circle - p1 # the directional vector from circle to p1\n",
    "            # t is where the line v(t) and the circle are closest\n",
    "            # Do not divide by zero if node1.p and node2.p are the same.\n",
    "            # In that case this will still check for collisions with circles\n",
    "            t = d12.dot(d1c) / (d12.dot(d12) + 1e-7)\n",
    "            t = max(0, min(t, 1)) # Our line segment is bounded 0<=t<=1\n",
    "            d = p1 + d12*t # The point where the line segment and circle are closest\n",
    "            is_collide = np.sum(np.square(center_circle-d)) < radius**2\n",
    "            if is_collide:\n",
    "                return True # is in collision\n",
    "        return False # is not in collision\n",
    "    \n",
    "    def final_path(self, goal_ind):\n",
    "        \"\"\"Compute the final path from the goal node to the start node\"\"\"\n",
    "        path = [self.goal.p]\n",
    "        node = self.node_list[goal_ind]\n",
    "        # modify here: Generate the final path from the goal node to the start node.\n",
    "        # We will check that path[0] == goal and path[-1] == start\n",
    "        return path\n",
    "\n",
    "    def draw_graph(self):\n",
    "        for node in self.node_list:\n",
    "            if node.parent:\n",
    "                plt.plot([node.p[0], node.parent.p[0]], [node.p[1], node.parent.p[1]], \"-g\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can view the result of your implementation below. If you did everything correctly, the RRT should be able to find a feasible path from the start to the goal location."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(7)\n",
    "rrt = RRT(start=start,\n",
    "          goal=goal,\n",
    "          bounds=bounds,\n",
    "          obstacle_list=obstacles)\n",
    "path_rrt = rrt.plan()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(6,6))\n",
    "plot_scene(obstacles, start, goal)\n",
    "rrt.draw_graph()\n",
    "if path_rrt is None:\n",
    "    print(\"No viable path found\")\n",
    "else:\n",
    "    plt.plot([x for (x, y) in path_rrt], [y for (x, y) in path_rrt], '-r')\n",
    "plt.tight_layout()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An RRT can also be considered as a Monte-Carlo method to bias search into the largest unoccupied regions of a graph in configuration space. This means that the tree preferably expands towards large unsearched areas. If your above implementation of the RRT is correct, you will be able to observe this behavior by investigating the tree at a different number of node expansions. It is worth taking some time to think about how this method of expanding the tree uniformly at random over the whole search space differs from breadth-first search or depth-first search."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "max_iter_array = [10, 20, 100, 300]\n",
    "plt.figure(figsize=(14,5))\n",
    "goal_out_of_bound = np.array([100,100])\n",
    "for i in range(4):\n",
    "    plt.subplot(1, 4, i+1)\n",
    "    np.random.seed(9)\n",
    "    rrt = RRT(start=start,\n",
    "              goal=goal_out_of_bound,\n",
    "              bounds=bounds,\n",
    "              obstacle_list=[],\n",
    "              goal_sample_rate=0.0, \n",
    "              max_iter=max_iter_array[i])\n",
    "    path = rrt.plan()\n",
    "    plot_scene([], start, goal_out_of_bound)\n",
    "    rrt.draw_graph()\n",
    "    plt.title('max_iter = {}'.format(max_iter_array[i]))\n",
    "plt.tight_layout()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# RRT*\n",
    "In the previous RRT example, we stopped the iteration once a path connecting the `start` and `goal` region was found without colliding with the obstacles. Instead of asking for <em>any</em> feasible solution, we may ask for the shortest path instead. To do so, we may continue expanding nodes in the tree. Nonetheless, it can be shown that the RRT algorithm almost always converges to a non-optimal solution.\n",
    "\n",
    "[RRT*](http://roboticsproceedings.org/rss06/p34.pdf) is an improved version of RRT which exhibits asymptotic optimality: When the number of nodes approaches infinity, the RRT* algorithm will deliver the shortest possible path to the goal. The basic principle of RRT* is the same as RRT, but (i) each node keeps track of the cost of the unique path from `start` to the node, and (ii) RRT* is essentially <em>rewiring</em> the tree as it discovers new lower-cost paths reaching the nodes that are already in the tree. You will code the rewiring part of the algorithm.\n",
    "\n",
    "**These are the main steps of the second part of the exercise:**\n",
    "1. Familiarize yourself with the RRTStar class. Go through the code, understand the components and see what has been implemented already that might come in handy later on.\n",
    "2. Complete the `choose_parent` method by following the instructions inside the method and the description below.\n",
    "3. Implement the `rewire` method.\n",
    "\n",
    "Note that you only have to change the code where indicated by `# modify here`.\n",
    "\n",
    "As mentioned above, RRT*'s main difference from RRT is the dynamic rewiring when sampling a new node. First, a new feasible node is sampled like in RRT. Then, the algorithm chooses the best parent for the new node from a set of nodes that are close to the new node. This basically describes the search for the lowest cost way of getting to the sampled new node from any other node. In principle, we could search over the whole graph but we limit ourselves to the close proximity to avoid poor scaling as the graph grows. The procedure of searching for the best parent should be implemented in `choose_parent`.\n",
    "\n",
    "In a second step, the `rewire` function checks whether the cost of the nodes in the vicinity of the sampled node can be decreased by rewiring them to the newly added node. If the cost can indeed be decreased, the neighbor is rewired to the newly added node.\n",
    "\n",
    "While this explanation should be enough to complete the exercise, it may be interesting to have a look at the original paper [here](http://roboticsproceedings.org/rss06/p34.pdf)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class RRTStar(RRT):\n",
    "    \n",
    "    class Node(RRT.Node):\n",
    "        def __init__(self, p):\n",
    "            super().__init__(p)\n",
    "            self.cost = 0.0\n",
    "\n",
    "    def __init__(self, start, goal, obstacle_list, bounds,\n",
    "                 max_extend_length=5.0,\n",
    "                 path_resolution=0.5,\n",
    "                 goal_sample_rate=0.0,\n",
    "                 max_iter=200,\n",
    "                 connect_circle_dist=50.0\n",
    "                 ):\n",
    "        super().__init__(start, goal, obstacle_list, bounds, max_extend_length,\n",
    "                         path_resolution, goal_sample_rate, max_iter)\n",
    "        self.connect_circle_dist = connect_circle_dist\n",
    "        self.goal = self.Node(goal)\n",
    "\n",
    "    def plan(self):\n",
    "        \"\"\"Plans the path from start to goal while avoiding obstacles\"\"\"\n",
    "        self.node_list = [self.start]\n",
    "        for i in range(self.max_iter):\n",
    "            # Create a random node inside the bounded environment\n",
    "            rnd = self.get_random_node()\n",
    "            # Find nearest node\n",
    "            nearest_node = self.get_nearest_node(self.node_list, rnd)\n",
    "            # Get new node by connecting rnd_node and nearest_node\n",
    "            new_node = self.steer(nearest_node, rnd, self.max_extend_length)\n",
    "            # If path between new_node and nearest node is not in collision:\n",
    "            if not self.collision(new_node, nearest_node, self.obstacle_list):\n",
    "                near_inds = self.near_nodes_inds(new_node)\n",
    "                # Connect the new node to the best parent in near_inds\n",
    "                new_node = self.choose_parent(new_node, near_inds)\n",
    "                self.node_list.append(new_node)\n",
    "                # Rewire the nodes in the proximity of new_node if it improves their costs\n",
    "                self.rewire(new_node, near_inds)\n",
    "        last_index, min_cost = self.best_goal_node_index()\n",
    "        if last_index:\n",
    "            return self.final_path(last_index), min_cost\n",
    "        return None, min_cost\n",
    "\n",
    "    def choose_parent(self, new_node, near_inds):\n",
    "        \"\"\"Set new_node.parent to the lowest resulting cost parent in near_inds and\n",
    "        new_node.cost to the corresponding minimal cost\n",
    "        \"\"\"\n",
    "        min_cost = np.inf\n",
    "        best_near_node = None\n",
    "        # modify here: Go through all near nodes and evaluate them as potential parent nodes by\n",
    "        # 1) checking whether a connection would result in a collision,\n",
    "        # 2) evaluating the cost of the new_node if it had that near node as a parent,\n",
    "        # 3) picking the parent resulting in the lowest cost and updating\n",
    "        #    the cost of the new_node to the minimum cost.\n",
    "        \n",
    "        # Don't need to modify beyond here\n",
    "        new_node.cost = min_cost\n",
    "        new_node.parent = best_near_node\n",
    "        return new_node\n",
    "    \n",
    "    def rewire(self, new_node, near_inds):\n",
    "        \"\"\"Rewire near nodes to new_node if this will result in a lower cost\"\"\"\n",
    "        # modify here: Go through all near nodes and check whether rewiring them\n",
    "        # to the new_node would: \n",
    "        # A) Not cause a collision and\n",
    "        # B) reduce their own cost.\n",
    "        # If A and B are true, update the cost and parent properties of the node.\n",
    "        \n",
    "        # Don't need to modify beyond here\n",
    "        self.propagate_cost_to_leaves(new_node)\n",
    "\n",
    "    def best_goal_node_index(self):\n",
    "        \"\"\"Find the lowest cost node to the goal\"\"\"\n",
    "        min_cost = np.inf\n",
    "        best_goal_node_idx = None\n",
    "        for i in range(len(self.node_list)):\n",
    "            node = self.node_list[i]\n",
    "            # Has to be in close proximity to the goal\n",
    "            if self.dist_to_goal(node.p) <= self.max_extend_length:\n",
    "                # Connection between node and goal needs to be collision free\n",
    "                if not self.collision(self.goal, node, self.obstacle_list):\n",
    "                    # The final path length\n",
    "                    cost = node.cost + self.dist_to_goal(node.p) \n",
    "                    if node.cost + self.dist_to_goal(node.p) < min_cost:\n",
    "                        # Found better goal node!\n",
    "                        min_cost = cost\n",
    "                        best_goal_node_idx = i\n",
    "        return best_goal_node_idx, min_cost\n",
    "\n",
    "    def near_nodes_inds(self, new_node):\n",
    "        \"\"\"Find the nodes in close proximity to new_node\"\"\"\n",
    "        nnode = len(self.node_list) + 1\n",
    "        r = self.connect_circle_dist * np.sqrt((np.log(nnode) / nnode))\n",
    "        dlist = [np.sum(np.square((node.p - new_node.p))) for node in self.node_list]\n",
    "        near_inds = [dlist.index(i) for i in dlist if i <= r ** 2]\n",
    "        return near_inds\n",
    "\n",
    "    def new_cost(self, from_node, to_node):\n",
    "        \"\"\"to_node's new cost if from_node were the parent\"\"\"\n",
    "        d = np.linalg.norm(from_node.p - to_node.p)\n",
    "        return from_node.cost + d\n",
    "\n",
    "    def propagate_cost_to_leaves(self, parent_node):\n",
    "        \"\"\"Recursively update the cost of the nodes\"\"\"\n",
    "        for node in self.node_list:\n",
    "            if node.parent == parent_node:\n",
    "                node.cost = self.new_cost(parent_node, node)\n",
    "                self.propagate_cost_to_leaves(node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(7)\n",
    "rrt_star = RRTStar(start=start,\n",
    "          goal=goal,\n",
    "          bounds=bounds,\n",
    "          obstacle_list=obstacles)\n",
    "path_rrt_star, min_cost = rrt_star.plan()\n",
    "print('Minimum cost: {}'.format(min_cost))\n",
    "\n",
    "# Check the cost\n",
    "def path_cost(path):\n",
    "    return sum(np.linalg.norm(path[i] - path[i + 1]) for i in range(len(path) - 1))\n",
    "\n",
    "if path_rrt_star:\n",
    "    print('Length of the found path: {}'.format(path_cost(path_rrt_star)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should be able to achieve a minimum path length below 17.5 if you implemented everything correctly and be able to see a characteristic fan-like pattern generated by the RRT* paths."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(6,6))\n",
    "plot_scene(obstacles, start, goal)\n",
    "rrt_star.draw_graph()\n",
    "if path_rrt_star is None:\n",
    "    print(\"No viable path found\")\n",
    "else:\n",
    "    plt.plot([x for (x, y) in path_rrt_star], [y for (x, y) in path_rrt_star], '-r')\n",
    "plt.tight_layout()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Autograding\n",
    "You can check your work by running the following cell."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from underactuated.exercises.planning.rrt_planning.test_rrt_planning import TestRRTPlanning\n",
    "from underactuated.exercises.grader import Grader\n",
    "Grader.grade_output([TestRRTPlanning], [locals()], 'results.json')\n",
    "Grader.print_test_results('results.json')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}